class Solution {//leetcode279——完全平方数
public:
    int numSquares(int n) {
        int cnt=sqrt(n);
        vector<int> dp(n+1) ;
        for(int j=1;j<n+1;j++){
            dp[j]=0x3f3f3f3f;
        }
        for(int i=1;i<cnt+1;i++){
            int x=i*i;
            for(int j=x;j<n+1;j++){
                dp[j]=dp[j];
                if(j>=x)dp[j]=min(dp[j],dp[j-x]+1);
            }
        }
        return dp[n];
    }
};